public class LeetCode69 {
    public int mySqrt(int x) {
        if (x < 2)
            return x; // 如果x小于2，直接返回x

        int left = 1, right = x / 2; // 初始化左右边界
        while (left <= right) {
            int mid = left + (right - left) / 2; // 使用除法而非位移操作来计算中间值
            if (mid == x / mid) { // 检查mid是否正好是平方根
                return mid;
            } else if (mid < x / mid) { // 如果mid太小
                left = mid + 1;
            } else { // 如果mid太大
                right = mid - 1;
            }
        }

        // 返回right是因为最后一次循环时，right会停在最大且平方不超过x的位置
        return right;
    }
}
